#include <iostream>
using namespace std;


int max3(int a,int b,int c)
{
    if(a>b) return a>c?a:c;
    else return b>c?b:c;
}


int MaxSubseqSum(int a[],int left,int right)
{
    if(left==right)
        return a[left];

    int mid=(left+right)/2;	//求中间位置
    int maxLeftSum=MaxSubseqSum(a,left,mid); //求左边序列的最大子序列和
    int maxRightSum=MaxSubseqSum(a,mid+1,right); //求右边序列的最大子序列和

    int maxLeftBorderSum=0;
    int LeftBorderSum=0;
    for(int i=mid;i>=left;i--) //从中间位置（注意顺序！）向左找靠边界的最大子序列
    {
        LeftBorderSum+=a[i];
        if(LeftBorderSum>maxLeftBorderSum)
            maxLeftBorderSum=LeftBorderSum;
    }

    int maxRightBorderSum=0;
    int RightBorderSum=0;
    for(int i=mid+1;i<=right;i++) //从中间位置向右找靠边界的最大子序列
    {
        RightBorderSum+=a[i];
        if(RightBorderSum>maxRightBorderSum)
            maxRightBorderSum=RightBorderSum;
    }

    int maxMidSum=maxLeftBorderSum+maxRightBorderSum; //得到处在中间位置上的最大子序列和
    return max3(maxLeftSum,maxRightSum,maxMidSum);
}


int main()
{
    int a[3]={2,-1,3};
    cout << MaxSubseqSum(a,0,2) << endl;
    return 0;
}
